import org.junit.jupiter.api.DisplayName;
import org.junit.jupiter.params.ParameterizedTest;
import org.junit.jupiter.params.provider.Arguments;
import org.junit.jupiter.params.provider.MethodSource;

import java.util.stream.Stream;

/**
 * 移动零
 * 题目：给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
 * <p>
 * 示例:
 * 输入: [0,1,0,3,12]
 * 输出: [1,3,12,0,0]
 * <p>
 * 来源：力扣（LeetCode-283）
 * 链接：https://leetcode-cn.com/problems/move-zeroes
 *
 * @author godfrey
 * @since 2020-11-03
 */
@DisplayName("移动零")
public class MoveZeroes extends BaseTest {

    static Stream<Arguments> testArguments() {
        return Stream.of(
                Arguments.arguments((Object) new int[]{0, 1, 0, 3, 12})
        );
    }

    @DisplayName("双指针两次遍历-时间复杂度O(n)，空间复杂度O(1)")
    @ParameterizedTest
    @MethodSource("testArguments")
    void moveZeroes(int[] nums) {
        int index = 0;
        for (int i = 0; i < nums.length; ++i) {
            if (nums[i] != 0) {
                nums[index++] = nums[i];
            }
        }
        for (int i = index; i < nums.length; ++i) {
            nums[i] = 0;
        }
    }

    @DisplayName("双指针一次遍历-时间复杂度O(n)，空间复杂度O(1)")
    @ParameterizedTest
    @MethodSource("testArguments")
    void moveZeroes2(int[] nums) {
        int j = 0;
        for (int i = 0; i < nums.length; ++i) {
            //当前元素!=0，就把其交换到左边，等于0的交换到右边
            if (nums[i] != 0) {
                //避免无效覆盖
                if (i > j) {
                    nums[j] = nums[i];
                    nums[i] = 0;
                }
                ++j;
            }
        }
    }
}
